package leetcode;

import java.util.LinkedList;

/**
 * Created by Ghost on 2014/12/8 0008.
 /*                            _ooOoo_
 /*                           o8888888o
 /*                           88" . "88
 /*                           (| -_- |)
 /*                            O\ = /O
 /*                        ____/`---'\____
 /*                      .   ' \\| |// `.
 /*                       / \\||| : |||// \
 /*                     / _||||| -:- |||||- \
 /*                       | | \\\ - /// | |
 /*                     | \_| ''\---/'' | |
 /*                      \ .-\__ `-` ___/-. /
 /*                   ___`. .' /--.--\ `. . __
 /*                ."" '< `.___\_<|>_/___.' >'"".
 /*               | | : `- \`.;`\ _ /`;.`/ - ` : | |
 /*                 \ \ `-. \_ __\ /__ _/ .-` / /
 /*         ======`-.____`-.___\_____/___.-`____.-'======
 /*                            `=---='
 /*
 /*         .............................................
 /*                  佛祖镇楼                  BUG辟易
 /*          佛曰:
 /*                  写字楼里写字间，写字间里程序员；
 /*                  程序人员写程序，又拿程序换酒钱。
 /*                  酒醒只在网上坐，酒醉还来网下眠；
 /*                  酒醉酒醒日复日，网上网下年复年。
 /*                  但愿老死电脑间，不愿鞠躬老板前；
 /*                  奔驰宝马贵者趣，公交自行程序员。
 /*                  别人笑我忒疯癫，我笑自己命太贱；
 /*                  不见满街漂亮妹，哪个归得程序员？

 */

/**
 * Important
 */
public class Jump_Game_II {

   public int jump(int[] A) {//look forward
       if (A == null || A.length <= 1) {
           return 0;
       }

       int tail = A[0];
       int min = 1;

       int begin = 0;
       while (tail < A.length - 1) {
           int maxPace = 0;
           for (int i = begin ; i <= tail; i++) {
               maxPace = Math.max(maxPace, i + A[i]);
           }
           begin = tail + 1;
           tail = Math.max(tail, maxPace);
           min++;
       }
       return min;
   }
    public static void main(String[] args){
        Jump_Game_II jump_game_ii = new Jump_Game_II();
        int i=25000;
        LinkedList<Integer> a = new LinkedList<Integer>();
        for(;i>=0;i--){
            a.add(i);
        }
    }
}
